package main

import "fmt"

func main() {
	nums := []int{1, 1, 1}
	k := 2
	fmt.Println(subarraySum(nums, k))
}

/**
 * @Description:1048ms  暴力破解，
 */
//func subarraySum(nums []int, k int) int {
//	count:=0
//	for end:=0;end<len(nums);end++{
//		result:=0
//		for start:=end;start>=0;start--{
//			result+=nums[start]
//			if result==k{
//				count++
//			}
//		}
//	}
//	return count
//}

/**
 * @Description: 48ms 利用前缀和+map，从左到右依次遍历数组，边计算前缀和，边往map里面存储当前值数量，count+=map[pre-k]
 */
func subarraySum(nums []int, k int) int {
	count := 0
	pre := 0
	tempMap := make(map[int]int)
	tempMap[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := tempMap[pre-k]; ok {
			count += tempMap[pre-k]
		}
		tempMap[pre] += 1
	}
	return count
}
